Description

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Answer & Explaining

建立HashTable

 #include <stdio.h>
 #include <stdlib.h>

 struct HashTableEntry {
    int key; // 數字本體
    int value; // 鍵值
    struct HashTableEntry* next; // 下個節點
 }; //remenber that the struct need a ';'

初始化與創建節點

 #define TABLE_SIZE 10000
// hash function

int hash(int key) { 
    return abs(key) % TABLE_SIZE; //確保節點位置
}

// HashTable創建節點
struct HashTableEntry* createEntry(int key, int value) {
    struct HashTableEntry* newEntry = (struct HashTableEntry*)malloc(sizeof(struct HashTableEntry)); //動態分佈記憶體，malloc返回HashTableEntry結構大小
    newEntry->key = key; //初始化節點的key, value
    newEntry->value = value;
    newEntry->next = NULL;
    return newEntry; //提供函數使用
};

插入與搜尋功能

//HashTable 插入節點
void insert(struct HashTableEntry** table, int key, int value){
    int hashIndex = hash(key);
    struct HashTableEntry* newEntry = createEntry(key, value);
    newEntry-> next = table[hashIndex];
    table[hashIndex] = newEntry;
}

//搜尋HashTable中的節點
int search(struct HashTableEntry** table, int key){
    int hashIndex = hash(key);
    struct HashTableEntry* entry = table[hashIndex];
    while (entry != NULL){ //遍歷所有鏈的key
        if (entry->key ==key) {
            return entry->value;
        }
        entry = entry->next;
    }
    return -1; //not found
}

TwoSum function

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    //初始化
    struct HashTableEntry* table[TABLE_SIZE] = {NULL};
    int* result = (int*)malloc(2*sizeof(int));
    
    for(int i=0;i< numsSize;i++){
        int complement = target - nums[i]; //補數為差值
        int complementIndex = search(table, complement);
        if(complementIndex != -1){
            result[0] = complementIndex;
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        insert(table, nums[i],i);
    }
    *returnSize = 0;
    return result;
}

使用範例

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);

    if (returnSize == 2) {
        printf("Indices: [%d, %d]\n", result[0], result[1]);
    } else {
        printf("No solution found.\n");
    }

    free(result); // 釋放記憶體
    return 0;
}